//
// Created by denglibin on 2020/6/14.
//
// 红黑树
/**
 红黑树的特性:
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
 关于它的特性，需要注意的是：
第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。
第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

 红黑树的基本操作是添加、删除和旋转。

 旋转包括两种：左旋 和 右旋
 */

#include <stdio.h>
#include <stdlib.h>

#define RED 0
#define BLACK 1

// 节点 结构体
typedef struct node
{
    unsigned char color; // 颜色 RED或BLACK
    int data;
    struct node *left;   // 左子节点
    struct node *right;  // 右子节点
    struct node *parent; // 父节点
} Node;

/**
 * 左旋操作
 * 左旋示意图(对节点x进行左旋)：
 *      px                              px
 *     /                               /
 *    x                               y
 *   /  \      --(左旋)-->           / \
 *  lx   y                          x  ry
 *     /   \                       /  \
 *    ly   ry                     lx  ly
 * @param node
 * @return 当前子树的根节点
 */
static Node *leftRotate(Node *node)
{
    Node *parent = node->parent; // 记录一下父节点
    int parentIsNull = parent == NULL;
    int isLeft = 0; // 传入节点是否是父节点的左节点
    if (!parentIsNull)
    {
        isLeft = node == parent->left;
    }
    Node *right = node->right;     // 右节点
    Node *rightLeft = right->left; //　右节点的左节点

    node->right = rightLeft;
    if (rightLeft != NULL)
    {
        rightLeft->parent = node;
    }

    node->parent = right;

    right->parent = parent;
    right->left = node;

    if (!parentIsNull)
    {
        if (isLeft)
        {
            parent->left = right;
        }
        else
        {
            parent->right = right;
        }
    }
    return right;
}

/**
 * 右旋
 * 右旋示意图(对节点y进行左旋)：
 *            py                               py
 *           /                                /
 *          y                                x
 *         /  \      --(右旋)-->            /  \
 *        x   ry                           lx   y
 *       / \                                   / \
 *      lx  rx                                rx  ry
 * @param node
 * @return 当前子树的根节点
 */
static Node *rightRotate(Node *node)
{
    Node *parent = node->parent;
    int parentIsNull = parent == NULL;
    int isLeft = 0; // 传入节点是否是父节点的左节点
    if (!parentIsNull)
    {
        isLeft = node == parent->left;
    }
    Node *left = node->left;
    Node *leftRight = left->right;

    node->left = leftRight;
    if (leftRight != NULL)
    {
        leftRight->parent = node;
    }

    node->parent = left;

    left->parent = parent;
    left->right = node;
    if (!parentIsNull)
    {
        if (isLeft)
        {
            parent->left = left;
        }
        else
        {
            parent->right = left;
        }
    }
    return left;
}

/**
 * 当做普通二叉查找树插入 新加入的节点为红色
 * @param node 根节点 不为NULL
 * @param val
 * @return 插入的节点
 */
static Node *binInsert(Node *node, int val)
{
    Node *temp = node;
    Node *tempParent;
    while (temp != NULL)
    {
        tempParent = temp;
        if (val < temp->data)
        {
            temp = temp->left;
        }
        else
        {
            temp = temp->right;
        }
    }
    temp = (Node *)calloc(1, sizeof(Node));
    temp->data = val;
    temp->color = RED;
    temp->parent = tempParent;
    if (val < tempParent->data)
    {
        tempParent->left = temp;
    }
    else
    {
        tempParent->right = temp;
    }
    return temp;
}

/**
 * 获取该节点的叔节点
 * @param node
 * @return
 */
static Node *uncleNode(Node *node)
{
    if (node == NULL || node->parent == NULL || node->parent->parent == NULL)
    {
        return NULL;
    }
    if (node->parent == node->parent->parent->left)
    {
        return node->parent->parent->right;
    }
    return node->parent->parent->left;
}
/**
 * 当前节点是父亲的左孩子，父亲是祖父的左孩子（Left-Left），处理思路：a.将祖父节点右旋;b.交换父节点和祖父节点的颜色
 * @param node
 * @return 当前子树的根节点
 */
static Node *leftLeft(Node *node)
{
    Node *p = node->parent;
    Node *pp = node->parent->parent;
    Node *newRoot = rightRotate(pp);
    unsigned char pColor = p->color;
    p->color = pp->color;
    pp->color = pColor;
    return newRoot;
}
/**
 * 前节点是父亲的右孩子，父亲是祖父的右孩子（Right-Right），处理思路：a.将祖父节点左旋;b.交换父节点和祖父节点的颜色
 * @param node
 * @return 当前子树的根节点
 */
static Node *rightRight(Node *node)
{
    Node *p = node->parent;
    Node *pp = node->parent->parent;
    Node *newRoot = leftRotate(pp);
    unsigned char pColor = p->color;
    p->color = pp->color;
    pp->color = pColor;
    return newRoot;
}
/**
 * 平衡操作(涂色或旋转)
 * @param root 根节点
 * @param newNode 新节点
 * @return
 */
static Node *balanceTree(Node *root, Node *newNode)
{
    Node *parent = newNode->parent;
    if (parent == NULL)
    { // 1）新节点位于根节点，其没有父节点时，处理思路：将该节点直接设为黑色即可
        root->color = BLACK;
        return root;
    }
    if (parent->color == BLACK)
    { // 2）新节点的父节点已然是黑色时，处理思路：不用动，这已然是一颗红黑树
        return root;
    }
    Node *uncle_Node = uncleNode(newNode);
    // 3）父节点和叔节点都是红色时，处理思路：a.将父节点和叔节点设为黑色;b.将祖父节点设为红色;c.将祖父节点设为当前节点，并继续对新当前节点进行操作
    if (parent->color == RED && uncle_Node != NULL && uncle_Node->color == RED)
    {
        parent->color = BLACK;
        uncle_Node->color = BLACK;
        parent->parent->color = RED;
        return balanceTree(root, parent->parent); // 递归
    }
    // 4) 父节点是红色，叔节点是黑色时，又分如下四种情况

    // 4.1)  当前节点是父亲的左孩子，父亲是祖父的左孩子（Left-Left），处理思路：a.将祖父节点右旋;b.交换父节点和祖父节点的颜色
    if (newNode == newNode->parent->left && newNode->parent == newNode->parent->parent->left)
    {
        Node *newRoot = leftLeft(newNode);
        if (newRoot->parent == NULL)
        {
            return newRoot;
        }
        return root;
    }
    // 4.2) 当前节点是父亲的右孩子，父亲是祖父的左孩子（Right-Left），处理思路：a.将父节点左旋，并将父节点作为当前节点; b.然后再使用Left Left情形
    if (newNode == newNode->parent->right && newNode->parent == newNode->parent->parent->left)
    {
        Node *p = newNode->parent;
        leftRotate(p);
        Node *newRoot = leftLeft(p);
        if (newRoot->parent == NULL)
        {
            return newRoot;
        }
        return root;
    }
    // 4.3) 前节点是父亲的右孩子，父亲是祖父的右孩子（Right-Right），处理思路：a.将祖父节点左旋;b.交换父节点和祖父节点的颜色
    if (newNode == newNode->parent->right && newNode->parent == newNode->parent->parent->right)
    {
        Node *newRoot = rightRight(newNode);
        if (newRoot->parent == NULL)
        {
            return newRoot;
        }
        return root;
    }
    // 4.4) 当前节点是父亲的左孩子，父亲是祖父的右孩子（Left-Right），处理思路：a.将父节点右旋，并将父节点作为当前节点; b.然后再使用Right Right情形
    if (newNode == newNode->parent->left && newNode->parent == newNode->parent->parent->right)
    {
        Node *p = newNode->parent;
        rightRotate(p);
        Node *newRoot = rightRight(p);
        if (newRoot->parent == NULL)
        {
            return newRoot;
        }
        return root;
    }
    return NULL;
}

/**
 * 红黑树插入
 * @param node 根节点 没有传NULL
 * @param val
 * @return
 */
static Node *insert(Node *node, int val)
{
    if (node == NULL)
    { // 一个节点都没有
        node = (Node *)calloc(1, sizeof(Node));
        node->data = val;
        node->color = BLACK; // 根节点为黑色
        return node;
    }
    // 作为普通二叉查找树插入
    Node *newNode = binInsert(node, val);
    node = balanceTree(node, newNode); //平衡
    return node;
}
/**
 * 先序遍历
 * @param root
 */
static void preOrderTraverse(Node *root, int deep)
{
    if (root)
    {
        for (int i = 0; i < deep; i++)
        {
            printf("- ");
        }
        printf("%d ", root->data);
        if (root->color == RED)
        {
            printf("RED\n");
        }
        else
        {
            printf("BLACK\n");
        }

        preOrderTraverse(root->left, deep + 1);  // 左 子树
        preOrderTraverse(root->right, deep + 1); // 右 子树
    }
}
int main29()
{

    int arr[20] = {12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17};
    Node *root = NULL;
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    {
        root = insert(root, arr[i]);
    }
    preOrderTraverse(root, 0);
    return 0;
}
